package leetcode_day._2021._202108._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/15 10:27
 * 出界的路径数
 * 算法：动态规划
 * dp[k][i][j] 表示到 [i, j] 这点的路径数
 * 依次遍历每个点
 */
public class _15_576 {
    public static void main(String[] args) {
        System.out.println(new _15_576().findPaths_upgrade(2, 2, 2, 0, 0));
    }

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int ans = 0;
        int mod = 1000000007;
        int[][][] dp = new int[maxMove + 1][m][n];
        // 0 + 1 = 1
        dp[0][startRow][startColumn] = 1;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        // 外层每次循环，相当于走一次
        for (int k = 0; k < maxMove; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int count = dp[k][i][j];
                    // 相当于剪枝了
                    if (count > 0) {
                        for (int[] direction : directions) {
                            int newI = i + direction[0], newJ = j + direction[1];
                            if (newI >= 0 && newI < m && newJ >= 0 && newJ < n)
                                dp[k + 1][newI][newJ] = (dp[k + 1][newI][newJ] + count) % mod;
                            else ans = (ans + count) % mod;
                        }
                    }
                }
            }
        }
        return ans;
    }

    public int findPaths_upgrade(int m, int n, int maxMove, int startRow, int startColumn) {
        int ans = 0;
        int mod = 1000000007;
        int[][] dp = new int[m][n];
        dp[startRow][startColumn] = 1;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int k = 0; k < maxMove; k++) {
            int[][] newDp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int count = dp[i][j];
                    if (count > 0) {
                        for (int[] direction : directions) {
                            int newI = i + direction[0], newJ = j + direction[1];
                            if (newI >= 0 && newI < m && newJ >= 0 && newJ < n)
                                newDp[i][j] = (newDp[i][j] + count) % mod;
                            else ans = (ans + count) % mod;
                        }
                    }
                }
            }
            dp = newDp;
        }
        return ans;
    }

}
